package algorithm.sort;

import java.util.Arrays;
import java.util.Scanner;



public class QuickSort{

    static int n = 8;
    static int[] arr = {2,1,4,7,8,6,5,3};

    static void QuickSort(int[] arr){
        Qsort(0, arr.length-1);
    }

    static void Qsort(int low, int high){
        if (low < high) {
            int mid = partition(low, high);
            Qsort(low, mid - 1);
            Qsort(mid + 1, high);
        }
    }

    private static int partition(int start, int end) {
        int temp = arr[start];
        while (start < end) {
            while (end > start && arr[end] >= temp) {
                end--;
            }
            arr[start] = arr[end];
            while (end > start && arr[start] <= temp) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = temp;
        return start;
    }

    public static void main(String[] args) {
        QuickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}